/*
 * optitree.c
 *
 *  Created on: 3 nov. 2011
 *      Author: pmilian
 */
#include "algo.h"

static bool
depth_search(const Graph *graph, vector<int> * coverVertexes, int vertex,bool is_root){
	if ( graph->numEdge(vertex) == 1)
	{
		return false;
	}
	bool attrib_vertex = true;
	int i=(is_root)?0:1;
	for(;i<graph->numEdge(vertex);i++)
			attrib_vertex &= depth_search(graph, coverVertexes,graph->getNeighbours(vertex)[i],false);
	if(!attrib_vertex) {
			coverVertexes->push_back(vertex);
			return true;
	}
	return false;
}



vector<int> optitree(const Graph *graph){
	vector<int> * coverVertexes = new vector<int>();
	depth_search(graph,coverVertexes,0,true);
	return *coverVertexes;
}
